/*
  * @file RandomAlgorithm.cpp
  * @author Thibault Merle et Guillaume Poussel
  */
#include <algorithm>
#include <iterator>

#include "base/geometry.h"
#include "base/Vector.h"
#include "base/sorter.h"
#include "algo/RandomAlgorithm.h"

/**
  * @brief Calul de l'enveloppe convexe.
  *
  * @par "Complexité" Cette version est de complexité \f$O(n \log(n))\f$ et
  * utilise une stratégie \e randomisée.
  * @par "Algorithme" En partant d'un triangle, on choisit un point aléatoirement.
  * Si il est à l'intérieur du triangle, on le supprime. Sinon, on cherche
  * à agrandir le triangle. On répète le processus pour tous les points.
  * Le polygone résultant sera l'enveloppe convexe de l'ensemble de points.
  *
  * @param data Liste des points en entrée
  * @return Liste des points constituant l'enveloppe convexe
  */
point_list RandomAlgorithm::compute(point_list data)
{
    point_list hull;
    if(data.size() <= 2) return data;
    // S'il y a deux points ou moins, l'enveloppe est constituée de tous les points
    data.shuffle();
    // On choisit trois points au hasard constituant le triangle initial (E)
    for (int i = 0; i < 3; ++i) {
        hull.push_back(data.pick_point());
    }

    while (are_on_row(hull[0], hull[1], hull[2])) {
        // Tant que le triangle initial est plat, on recherche un autre point
        Point* min = *min_element(hull.begin(), hull.end(), Lexicographic_Order());
        Point* max = *max_element(hull.begin(), hull.end(), Lexicographic_Order());
        hull.clear();
        hull.push_back(min);
        hull.push_back(max);
        hull.push_back(data.pick_point());
    }


    // On choisit un point t dans le triangle, le barycentre par exemple
    Point* t = hull.get_centroid();

    // On trie les points de l'enveloppe dans le sens horaire
    hull.sort(Clockwise_Order(t, hull.front(), true));

    // Ensuite, on choisit dans un ordre aléatoire tous les autres points de l'ensemble (data), un par un.
    // Quand on choisit un point p, on regarde s'il est à l'interieur de E, sinon on complete E.

    unsigned size = hull.size();
    while(!data.empty()) {
        Point* p = data.pick_point();
        Segment p_t_seg (p,t);
        point_list::iterator itB = hull.begin();
        point_list::iterator itA = hull.next_point(itB);
        Segment sPol(*itB,*itA); // Le segment BA est sur l'enveloppe
        // On parcourt alors tous les segments de l'enveloppe jusqu'à
        // trouver le segment qui est coupé (si il existe)

        do {
            hull.advance(itA);
            hull.advance(itB);
            sPol = Segment(*itB,*itA);
        } while (!p_t_seg.intersect_segment(&sPol) && itB != hull.begin());
        if (p_t_seg.intersect_segment(&sPol)) {
            // Le point est à l'extérieur du polygone puisqu'on a trouvé une
            // intersection. Il faut maintenant trouver les points à supprimer

            point_list::iterator itRight = hull.next_point(itA);
            Vector v1(*itA,*itRight),v2(*itA,p);
            // On cherche maintenant les points à supprimer à l'aide
            // des côtés visibles par le point p situé à l'extérieur
            // Parcours dans le sens horaire
            while (size > 2 && cross_product(&v1, &v2) >= 0) {
                --size;
                itA = hull.erase(itA);
                if(itA == hull.end()) {
                    itA = hull.begin();
                }
                itRight = hull.next_point(itA);
                v1 = Vector(*itA, *itRight);
                v2 = Vector(*itA, p);
            }
            itB = hull.prev_point(itA);

            point_list::iterator itLeft = hull.prev_point(itB);
            v1 = Vector(*itB, *itLeft);
            v2 = Vector(*itB, p);
            // Parcours dans le sens anti-horaire
            while (size > 2 && cross_product(&v1, &v2) <= 0) {
                --size;
                itB = hull.erase(itB);
                hull.move_back(itB);
                itLeft = hull.prev_point(itB);
                v1 = Vector(*itB, *itLeft);
                v2 = Vector(*itB, p);
            }
            // Finalement on insère le point p dans l'enveloppe
            ++size;
            hull.insert(itA, p);
        }
    }
    delete t;
    return hull;
}
